home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-02
/
pascala.zip
/
ASSIGN9.PAS
< prev
next >
Wrap
Pascal/Delphi Source File
|
1991-05-09
|
6KB
|
209 lines
(**********************************************)
(* ALEJO ALAMILLO *)
(* COSC 055 *)
(* ASST. #9 *)
(* SPRING 1991 *)
(**********************************************)
(*************************************************************)
(* Several procedures for binary tree processing are *)
(* contained in the module below. *)
(* This is NOT a complete module ready to link up with a *)
(* driver program. PRB 10/90 *)
(*************************************************************)
PROGRAM TreeMod(Input,Output);
TYPE DataType = Real;
NodePointer = ^NodeRec;
NodeRec= RECORD
Data: DataType;
Level: 0..Maxint;
LeftLink,RightLink: NodePointer;
END;
AverageOfTree = Array [0..25] of Integer;
StoreAverage = Array [1..50] of real;
Maxlevel = Array [1..50] of Integer;
VAR Root,CurrentNode: NodePointer;
Seed,Seedy,
NumofTrees,
P : Integer;
TotalAve : Real;
DataIn: DataType;
Max : Maxlevel;
Storeave:storeaverage;
Ave : AverageOfTree ;
(***************************************************)
(* Generates a random number ( 0 <= R < 1 ) *)
(* Seed must be initialized ONCE before using *)
(***************************************************)
FUNCTION Random(VAR Seed: Integer): Real;
CONST Modulus = 65536;
Multiplier = 25173;
Increment = 13849;
BEGIN
Seed:=((Multiplier*Seed) + Increment) MOD Modulus;
Random:= Seed/Modulus;
END;
(***************************************************)
(* Disposes of the nodes of an existing, unneeded *)
(* Tree. Recursively called in postorder. *)
(***************************************************)
PROCEDURE DisposeTree(VAR CurrentNode:NodePointer);
BEGIN
WITH CurrentNode^ DO
BEGIN
IF LeftLink <> NIL THEN
DisposeTree(LeftLink);
IF RightLink <> NIL THEN
DisposeTree(RightLink);
DisposeTree(CurrentNode);
END;
END;
(***************************************************)
(* Recursively searches for node to insert DataIn *)
(* Inserts data DataIn into a tree in order *)
(***************************************************)
PROCEDURE AddaNode(VAR Current: NodePointer;
DataIn: DataType;
CurrentLevel: Integer);
BEGIN
IF Current = nil THEN (* Place is found *)
BEGIN
New(Current);
Current^.Data:= DataIn;
Current^.Level:= CurrentLevel;
Current^.LeftLink:= nil;
Current^.RightLink:= nil;
END
ELSE (* Search farther *)
IF (DataIn < Current^.Data) THEN
AddaNode(Current^.LeftLink, DataIn, CurrentLevel+1)
ELSE
AddaNode(Current^.RightLink, DataIn,CurrentLevel+1); (* Duplicate keys *)
END; (* are inserted in *)
(* original order *)
(**************************************)
(* *)
(**************************************)
PROCEDURE FormTree(VAR Root:NodePointer);
CONST NumberofNodes = 127;
VAR I: Integer;
DataIn: DataType;
(*************************************)
(* Currently randomly generated *)
(*************************************)
PROCEDURE GetData(VAR DataIn: DataType);
BEGIN
DataIn:=100*Random(Seed)+1;
END;
BEGIN (* FormTree *)
Root:= nil;
FOR I:= 1 TO NumberofNodes DO
BEGIN
GetData(DataIn);
AddaNode(Root, DataIn, 0);
END;
END;
(**********************************************)
(* ShowTree Recursively displays a tree *)
(* in L-R order. *)
(**********************************************)
PROCEDURE ShowTree(CurrentNode: NodePointer);
BEGIN
WITH CurrentNode^ DO
BEGIN (* Reversed for rotated display *)
IF RightLink<> nil THEN
ShowTree(RightLink);
Writeln(' ',Trunc(Data):3*(1+Level));
IF LeftLink<>nil THEN
ShowTree(LeftLink);
END;
END;
(*****************************************************************)
(* This Procedure puts the level of each node into an array *)
(*****************************************************************)
Procedure FindAve (Current : NodePointer;
Var Ave :AverageOfTree ;
VAR StoreAve:StoreAverage;
NumofTrees:Integer);
Var C,Total, Levels : Integer;
TreeAve : Real;
Begin
With Current^ do
Begin
IF rightlink <> Nil then
FindAve (rightlink,Ave,StoreAve,NumofTrees);
Ave[level] := Ave[level] + 1;
IF leftlink <> Nil then
FindAve(leftlink,ave,StoreAve,NumofTrees);
Total := 0;
For C := 1 to 25 do
Begin
Levels := Ave[C] * C;
Total := Total + levels;
End;
Treeave := Total / 127;
StoreAve[NumofTrees] := TreeAve;
End;
End;
(**************************************************************)
(* This procedure finds the maximum level for each tree *)
(**************************************************************)
Procedure FindMax (Ave: AverageOfTree ; Var Max : Maxlevel; NumofTrees: Integer);
Var I, Maximum: Integer;
Begin
I := 26;
Repeat
I := I - 1;
Maximum := I;
until ave[I] <> 0;
Max[NumofTrees] := maximum;
End;
BEGIN (************* MAIN *************)
(* Initialize *)
Seed := 0;
(* Describe *)
Write('Enter a Seed value for the random generator: ');
Readln(Seedy);
For NumofTrees := 1 to 50 do
Begin
Seed := NumofTrees * Seedy;
FormTree(Root);
FindAve(Root,Ave,StoreAve,NumofTrees);
FindMax(Ave,Max,NumofTrees);
For p := 1 to 25 do
Ave[p]:=0;
End;
Writeln;
Writeln('Maximum Level Average Level');
Writeln;
For P := 1 to 50 do
Begin
Writeln(Max[P]:4,' ',StoreAve[P]:4:2);
TotalAve := TotalAve + StoreAve[P];
End;
TotalAve := TotalAve / 50;
Writeln('The average level for 50 trees is: ',TotalAve:4:2);
END.